1406E - Deleting Numbers - CodeForces Solution

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

#define DEBUG

bool nonPrimeTable[101005];
int aboveSqrtPrimeList[101005];
int aboveSqrtPrimeCount;
// 1~100000有9592個質數
// 10000-9592 = 408
// 408-
// 可以先對sqrt(100000)=316.227以內的質數用B A來query (65個*2 = 130), sqrt(100000)以外的質數用BBBBBBBA來二分搜
bool inSqrtStrat = true;
int currentQuery = 2;
int tmpQuery = -1;
int n;
int lrange = -1, rrange = -1;

int main() {
	cin >> n;
	if (n == 1) {
		cout << "C 1" << endl;
		fflush(stdout);
	}
	for (int i = 2; i <= sqrt(101000); ++i) {
		if (nonPrimeTable[i]) {
			continue;
		}
		for (int j = i+i; j <= 101000; j+=i) {
			nonPrimeTable[j] = true;
		}
	}
	for (int i = sqrt(n)+1; i <= n; ++i) {
		if (!nonPrimeTable[i]) {
			aboveSqrtPrimeList[aboveSqrtPrimeCount++] = i;
		}
	}
	lrange = 0;
	rrange = aboveSqrtPrimeCount-1;
	// initial query
	int currentQuery = 2;
	int queryNum;
	int answer = 1;
	while (true) {
		if (currentQuery <= sqrt(n)) {
			cout << "B " << currentQuery << endl;
			fflush(stdout);
			cin >> queryNum;
			cout << "A " << currentQuery << endl;
			fflush(stdout);
			cin >> queryNum;

			if (queryNum != 0) {
				// 如果已經用B刪掉currentQuery的話 照理來講queryNum應該要都是0
				// 如果queryNum不是0代表x是currentQuery的倍數
				int tmpQuery = currentQuery;
				do {
					tmpQuery *= currentQuery;
					if (tmpQuery > n) {
						break;
					}
					cout << "B " << tmpQuery << endl;
					fflush(stdout);
					cin >> queryNum;
					cout << "A " << tmpQuery << endl;
					fflush(stdout);
					cin >> queryNum;
				} while (queryNum >= 1);
				answer *= (tmpQuery / currentQuery);
			}
			while (nonPrimeTable[++currentQuery]);

		} 
		// if (answer > sqrt(n)) {
		// 	cout << "C " << answer << endl;
		// 	fflush(stdout);
		// 	break;
		// }
		if (currentQuery > sqrt(n)) {
			if (answer * currentQuery > n) {
				cout << "C " << answer << endl;
				fflush(stdout);
				break;
			} else {
				if (answer != 1) {
					for (int i = n/answer+1; i >= 1; --i) {
						if (!nonPrimeTable[i]) {
							rrange = i;
							break;
						}
					}
					for (int i = lrange; i <= rrange; ++i) {
						if (answer * aboveSqrtPrimeList[i] > n) {
							cout << "C " << answer << endl;
							fflush(stdout);
							break;
						}
						cout << "A " << answer * aboveSqrtPrimeList[i] << endl;
						fflush(stdout);
						cin >> queryNum;
						if (queryNum == 1) {
							cout << "C " << answer * aboveSqrtPrimeList[i] << endl;
							fflush(stdout);
							break;
						}
					}
					break;
				}
				if (lrange == rrange) {
					// test lrange and 1
					cout << "B " << aboveSqrtPrimeList[lrange] << endl;
					fflush(stdout);
					cin >> queryNum;
					cout << "A " << aboveSqrtPrimeList[lrange] << endl;
					fflush(stdout);
					cin >> queryNum;
					if (queryNum == 0) {
						cout << "C " << answer << endl;
						fflush(stdout);
						break;
					} else {
						cout << "C " << answer * aboveSqrtPrimeList[lrange] << endl;
						fflush(stdout);
						break;
					}
				}
				int mid = (lrange + rrange) / 2;
				if (rrange - lrange + 1 == 2) {
					// test all
					bool foundAns = false;
					for (int i = lrange; i <= rrange; ++i) {
						cout << "B " << aboveSqrtPrimeList[i] << endl;
						fflush(stdout);
						cin >> queryNum;
						cout << "A " << answer * aboveSqrtPrimeList[i] << endl;
						fflush(stdout);
						cin >> queryNum;
						if (queryNum == 1) {
							cout << "C " << answer * aboveSqrtPrimeList[i] << endl;
							fflush(stdout);
							foundAns = true;
							break;
						} else {
							continue;
						}
					}
					if (!foundAns) {
						cout << "C " << answer << endl;
						fflush(stdout);
						break;
					} else {
						break;
					}
				} else {
					while (rrange - mid == mid - lrange + 1) {
						// 2381 2381
						// left possible range after reduce 0, 1
						// right possible range 
						// [5 6] failed
						// [5 6 7]
						// [5 6 7 8]
						mid++;
					}
				}
				for (int i = lrange; i <= mid; ++i) {
					cout << "B " << aboveSqrtPrimeList[i] << endl;
					fflush(stdout);
					cin >> queryNum;
				}
				cout << "A 1" << endl;
				fflush(stdout);
				cin >> queryNum;
				#ifdef DEBUG
				cerr << lrange << " " << mid << " " << aboveSqrtPrimeList[mid] << " " << rrange << endl;
				#endif
				bool foundAns_loop = false;
				if (queryNum == 1 + (rrange - mid)) {
					// in the right region
					lrange = mid + 1;
				} else {
					// in the left region
					rrange = mid;
					for (int i = lrange; i <= rrange; ++i) {
						cout << "A " << aboveSqrtPrimeList[i] << endl;
						fflush(stdout);
						cin >> queryNum;
						if (queryNum == 1) {
						// in the right region
							cout << "C " << answer * aboveSqrtPrimeList[i] << endl;
							fflush(stdout);
							foundAns_loop = true;
							break;
						}
					}
					if (!foundAns_loop) {
						cout << "C " << answer << endl;
						fflush(stdout);
						break;
					}
				}
				if (foundAns_loop) {
					break;
				}
			}
		}
	}
}